第8章 排序算法与查找
排序是我们在实际应用中最多的一种场景，一般来说主要分为排序、查找，这两种场景使用都比较多。
在本章我们将对几种常见的排序算法进行讲解，目的是帮助我们可以更深入的理解算法、数据结构。
同时我们也将针对查找算法进行讲解，其中包括线性查找、二分查找以及一些常用的查找算法。
在之前我们讲解的数据结构中，其实已经涉及到了一些排序、查找的操作，比如链表的查找、大小堆、哈希查找。
通过本章的学习，我们可以掌握常用的冒泡、选择、插入、堆、快速、归并排序方式，以及常用的查找算法。
几种算法复杂度总结
| 算法 | 最好情况时间复杂度 | 最坏情况时间复杂度 | 平均情况时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) |
| 线性查找 | O(n) | O(n) | O(n) | O(1) |
| 二分查找 | O(1) | O(log n) | O(log n) | O(1) |